#include<iostream> 
using namespace std;
//72 6 57 88 60 42 83 73 48 85
void quickSort(int *arr,int left,int right){
 if(left<right){//判断有无坑位
  int x = arr[left],i = left,j = right;  
  while(i<j){
   while(j>i && arr[j]>=x) j--;//寻找坑位
   //此处一定不要忘了加判断条件if(arr[j]<x)
   //不然又可能是j=i而跳出的循环
   if(arr[j]<x) arr[i++] = arr[j];//填坑  
   while(i<j && arr[i]<=x) i++;//寻找坑位
   if(arr[i]>x) arr[j--] = arr[i];//填坑
  }
  arr[i] = x;//填坑
  quickSort(arr,left,i-1);//处理左区间
  quickSort(arr,i+1,right);//处理右区间     
 }  
}

//测试函数
int main(){
 int arr[10] = {72,6,57,88,60,42,83,73,48,85};
 for(int i = 0; i < 10;i++)
  cout<<arr[i]<<' ';
 cout<<endl;
 quickSort(arr,0,9);
 for(int i = 0; i < 10;i++)
  cout<<arr[i]<<' ';
 cout<<endl;
 return 0;
}